package com.lw.leetcode.dp.c;

import com.lw.leetcode.tree.TreeNode;

/**
 * Created with IntelliJ IDEA.
 * c
 * tree
 * https://leetcode.cn/contest/hhrc2022/problems/wFtovi/
 * 题目-04. 补给覆盖 MinSupplyStationNumber
 * 968. 监控二叉树
 * @author liw
 * @version 1.0
 * @date 2022/5/18 16:02
 */
public class MinCameraCover {


    public static void main(String[] args) {
        MinCameraCover test = new MinCameraCover();

        //
        TreeNode instance15 = TreeNode.getInstance15();

        int i = test.minCameraCover(instance15);
        System.out.println(i);
    }

    private int t = (1 << 10) - 1;
    private int f = (1 << 20) + (t << 10);

    public int minCameraCover(TreeNode root) {
        int v = find(root);
        int a1 = v >> 20;
        int a2 = (v >> 10) & 0X3FF;
        int a3 = v & 0X3FF;
        return Math.min(a1, Math.min(a2, a3 + 1));
    }

    private int find(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int l = find(root.left);
        int r = find(root.right);
        if (l == 0 && r == 0) {
            return f;
        }
        if (l == 0 || r == 0) {
            l = Math.max(l, r);
            r = 0;
        }
        int a1 = l >> 20;
        int a2 = (l >> 10) & 0X3FF;
        int a3 = l & 0X3FF;
        int c1;
        int c2;
        int c3;
        if (r == 0) {
            c1 = Math.min(a1, Math.min(a2, a3)) + 1;
            c2 = a1;
            c3 = Math.min(a1, a2);
        } else {
            int b1 = r >> 20;
            int b2 = (r >> 10) & 0X3FF;
            int b3 = r & 0X3FF;
            c1 = Math.min(a1, Math.min(a2, a3)) + Math.min(b1, Math.min(b2, b3)) + 1;
            c2 = Math.min(a1 + Math.min(b1, b2), b1 + Math.min(a1, a2));
            c3 = Math.min(a2 + Math.min(b1, b2), b2 + Math.min(a1, a2));
            c3 = Math.min(c3, t);
        }
        return (c1 << 20) + (c2 << 10) + c3;
    }

}
